package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/pascals-triangle-ii/'>杨辉三角 II(Pascal's Triangle II)</a>
 * <p>给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。</p>
 * <p>在「杨辉三角」中，每个数是它左上方和右上方的数的和。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: rowIndex = 3
 *      输出: [1,3,3,1]
 *
 * 示例 2:
 *      输入: rowIndex = 0
 *      输出: [1]
 *
 * 示例 3:
 *      输入: rowIndex = 1
 *      输出: [1,1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li> 0 <= numRows <= 33</li>
 * </ul>
 * </p>
 * <b>你可以优化你的算法到 O(rowIndex) 空间复杂度吗？</b>
 *
 * @author c2b
 * @since 2022/5/18 16:44
 */
public class LC0119PascalsTriangle_II_S {

    static class Solution {
        public List<Integer> getRow(int rowIndex) {
            // 前一行的集合
            List<Integer> prevList = new ArrayList<>();
            for (int i = 1; i <= rowIndex + 1; i++) {
                // 当前行的集合
                List<Integer> currList = new ArrayList<>();
                for (int j = 1; j <= i; j++) {
                    if (j == 1 || j == i) {
                        currList.add(1);
                    } else {
                        currList.add(prevList.get(j - 2) + prevList.get(j - 1));
                    }
                }
                prevList = currList;
            }
            return prevList;
        }

        /**
         * 使用数学公式，最优解
         */
        public List<Integer> getRow2(int rowIndex) {
            List<Integer> row = new ArrayList<>();
            row.add(1);
            for (int i = 1; i <= rowIndex; ++i) {
                row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i));
            }
            return row;
        }
    }


}
